1. Field of the Invention
The present invention relates to a digital watermark embedding apparatus, method and program for generating embedded codes corresponding to identification information, and embedding the codes into copies of contents, and a watermark analysis apparatus, method and program for extracting the identification information corresponding to the codes embedded in copies of contents used for collusive attacks.
2. Description of the Related Art
Digital contents (such as still images, moving images, sound, music, etc.) comprise a number of digital data items. Some of the data items can be changed, without altering the identity and monetary value of the digital contents. By doing this, various types of information can be embedded into digital contents. This is watermarking, a well-known technique.
Watermarking enables various types of watermark information to be embedded in digital contents, and to be detected and used for various purposes (such as copyright protection including control of use and/or copy). Watermark information includes, for example, information for identifying the owner of copyright or user of digital contents, right information for the owner of copyright, the condition of use of contents, secret information needed to use contents, copy control information, or a combination of the above.
A description will now be given of a technique used, for example, for embedding, into copies of digital contents, information for individually identifying the copies (such as watermark information precisely corresponding to each user ID), when the same digital contents are distributed to a number of users.
The technique of embedding identification information (or a code corresponding to this information) into each copy of digital contents can suppress illegal copying of digital contents, and protect the owner's copyright from copyright violation since when pirate copies appear on the market, the software pirate can be detected from the identification information of the pirate copy.
Further, if a user tries to invalidate identification information embedded in a copy of digital contents, they need to make significant alterations to it, since they do not know which bit corresponds to the identification information (or the code corresponding to the identification information), which may result in damage to the contents. This would be financially disadvantageous, thus may act as deterrence against illegal copying.
To overcome the above, a so-called “collusive attack” method has appeared.
The principle behind “collusive attacks” lies in the fact that different copies are embedded with different identification information items. For example, a plurality of users get together, and compare bit units of a number of copies, thereby detecting portions in which digital data differs. The identification information is altered or eliminated when the detected portions are altered (by, for example, majority decision, minority decision, randomization, etc.). Another method involves averaging the pixel values, which alters or eliminates the identification information.
This will be explained briefly. Assume that the following identification information items (actually, codes corresponding to the information items) A, B and C are embedded in the copies owned by persons A, B and C:
A: 10 . . . 00 . . .
B: 00 . . . 11 . . .
C: 11 . . . 01 . . .
In this case, information (code) 10 . . . 01 . . . , which differs from all the identification codes of the persons A, B and C, can be created by majority decision or averaging.
As a countermeasure against collusive attacks, there have been proposed various methods for embedding, as a digital watermark, a code (called a collusion resistance code) having a resistance against collusive attacks, i.e., a code for detecting some or all of the persons responsible for collusive attacks when the collusive attacks have occurred. Further, various tracing algorithms (for detecting an identification number embedded in contents and used for collusive attacks, thereby detecting the IDs of users of collusion) have been proposed. Theses algorithms are based on, for example, a c-secure code (disclosed in D. Boneh and J. Shaw, “Collusion-Secure Fingerprinting for Digital Data” Advance in Cryptology: Proceedings of CRYPTO'95, Springer-Verlag, pp. 452-465, 1995) or a c-secure CRT code (H. Muratani, “A Collusion-Secure Fingerprinting Codes Reduced by Chinese Remaindering and its Random-Error Resilience”, Information Hiding Proceedings of the 4th International Workshop, IH 2001, pp. 303-315, 2001, or in Jpn Pat. Appln. KOKAI Publication No. 2001-285623).
The c-secure CRT code will be described briefly.
The c-secure CRT code has an adjacency code structure in which a number M of component codes are arranged adjacent to each other. For example, the i-th component code W(i) is a bit sequence of a predetermined length that consists of only “0” bits, only “1” bits, or “0” and “1” bits (but, there is only one boundary between a series of “0” bits and a series of “1” bits). The number of “0” bits and “1” bits included in the component code W(i), i.e., the boundary position of the “0” bit series and “1” bit series of the component code W(i), is determined on the basis of the residual obtained by dividing identification information u by modular p(i).
For example, assume that M=3, p(1)=3, p(2)=5, p(3)=7, and “Γ0(n, d) code” is used as the component code W(i) (d=3), and identification information=user ID, the “Γ0(n, d) code” indicating a series of B(0)˜B(n−2), B(j) indicating a series of “0” or “1” bits, B(0)˜B(n−2) being formed of only “0” bits or “1” bits, or formed of a combination of B(0)˜B(m−1) consisting of only “0” bits and B(m)˜B(n−2) consisting of only “1” bits.
In this assumption, a code corresponding to user ID=2 is:
000000 000000111111 00000011111111111
Further, a code corresponding to user ID=3 is:
111111 000000000111 000000000111111111
In this case, if the contents brought by two users of user ID=2 and user ID=3 are compared, it is found that the first to sixth bits, thirteenth to fifteenth bits and twenty-fifth to twenty-seventh bits from the left differ between the two 36-bit codes. Since these bits are found to be the part of each code that corresponds to identification information, the first to sixth bits, thirteenth to fifteenth bits and twenty-fifth to twenty-seventh bits from the left are altered into, for example, the following code that differs from user ID=2 and user ID=3:
010101 000000010111 000000010111111111
However, a code corresponding to a legal user ID does not have a portion in which a number of “1” or “0” bits less than a predetermined block size d (in the above case, d=3) exist. On the other hand, different portions of the codes detected from the contents used for collusive attacks contain both “0” and “1” bits. In other words, there are portions in which “0” or “1” bits less than a number d of bits (3 bits in the above case) exist isolatedly.
In light of this, in the tracing algorithm, each component of a detected code is checked. If there is a component code in which “0” or “1” bits less than a predetermined number d of bits (3 bits in the above case) exist isolatedly, it is determined that collusive attacks were made to the detected code.
In the c-secure CRT code, the sum of the maximum residual and minimum residual (a pair of residuals) is equal to a residual u mod p(i) for identification information u concerning a person responsible for collusion. The minimum residual indicates the position of the boundary (or an integer value indicative of the position) between an element containing only “0” bits, and an element containing a “1” bit, which appears for the first time when the i-th component code W(i) of a code detected from to-be-traced contents is checked beginning from the leftmost bit. The maximum residual indicates the position of the boundary (or an integer value indicative of the position) between an element containing only “1” bits, and an element containing a “0” bit, which appears for the first time when the i-th component code W(i) of the detected code is checked beginning from the rightmost bit. If the i-th component code W(i) consists of only “0” bits, the maximum residual=minimum residual=p(i)−1. If the i-th component code W(i) consists of only “1” bits, the maximum residual=minimum residual=0. If there is no boundary between an element containing only “0” bits and an element containing a “1” bit, the minimum residual=0. If there is no boundary between an element containing only “1” bits and an element containing a “0” bit, the maximum residual=p(i)−1.
Thus, part of or the entire identification information that would have been embedded in a copy used for collusive attacks can be obtained by analyzing a pair of residuals extracted from each component code of a c-secure CRT code detected from to-be-traced contents.
In the above-described case, identification information, user ID=2 and user ID=3, relating to the people responsible for collusion, is detected from the following code:
010101 000000010111 000000010111111111
This c-secure CRT code is based on the following marking assumption. That is, if a person responsible for collusion has a code in which a certain bit of a component code has a different value from that of the codes owned by the other people, the value of the corresponding bit of a component code created as a result of collusive attacks is determined stochastically. Accordingly, if the block size d is relatively large, the minimum and maximum residuals can be correctly detected.
In the c-secure CRT code, there may be a case where the minimum and maximum residuals cannot correctly be detected from to-be-traced contents.
For example, in the case of collusive attacks made by one hundred people, assume that a “0”-bit sequence is assigned to ninety-nine people and a “1”-bit sequence is assigned to the remaining one person in corresponding blocks of corresponding component codes. In the marking assumption, it is expected that a sequence of “1” and “0” bits is detected with a certain probability. However, in digital watermarking, in most cases, bit value determination is executed on the basis of whether or not a certain measurement amount exceeds a predetermined threshold value. If collusive attacks utilize contents averaging, the amount of measurement after collusive attacks is expected to be an average amount of measurement made before the collusive attacks. Specifically, in the case of averaging of 99 versus 1, the influence of the ninety-nine people side measurement amount is dominant, and it is highly probable that the value of the bit sequence is detected to be 0 that is ninety-nine people side value. If the above-mentioned block is one in which minimum and maximum residuals are to be detected, they cannot correctly be detected.